DFS和BFS

Posted on | Post modified: | In |
Words count in article: 2.2k

DFS与BFS

DFS模板

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x) {
    if (get a result) {
        store the result;
        return ;
    }
    
    for (enumerate all possible states){
        if (have been visited) continue;
        visited[state] = true;
        
    }
}

八数码

该题的一个关键是状态表示，如何判断9个数字都归位了，这里用的方法是将它们压缩到一个string中，通过判断string是否相等来确认是否归位。通过哈希表来保存每个状态的最少交换次数，string是一维的，而实际上其中的数字具有二维的空间关系，使用除和余来提取这种关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string &start) {
    queue<string> q;
    unordered_map<string, int> dist;
    
    string end = "12345678x";
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty()) {
        string cur = q.front();  // 状态表示，使用string来表示9个位置
        q.pop();
        if (cur == end) return dist[cur];
        
        int pos = cur.find('x');
        int x = pos / 3, y = pos % 3;   // 获取x的位置的二维表示
        int distant = dist[cur];
        for (int i = 0; i < 4; ++ i ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 3 && a >= 0 && b < 3 && b >= 0) { // 交换的位置是否合法
                // 交换
                swap(cur[a * 3 + b], cur[pos]);
                if (!dist.count(cur)) {
                    q.push(cur);
                    dist[cur] = distant + 1;
                }
                // 还原
                swap(cur[a * 3 + b], cur[pos]);
            }
        }
    }
    return -1;   // 失败
}

int main() {
    char c[2];
    string s;
    for (int i = 0; i < 9; ++ i) {
        cin >> c;
        s += *c;
    }
    
    cout << bfs(s) ;
    return 0;
}

图上DFS和BFS

树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10, M = 2 * N;

int h[N], v[M], ne[M], idx;
bool st[N];
int n, res = N;

void add(int a, int b) {
    v[idx] = b, ne[idx] = h[a], h[a] = idx ++; // 头插法
    // v[idx] : 当前下标所指顶点， ne[idx]：当前下标的下一个节点的下标， h[a]：a的头节点的第一个节点
}

// 返回当前节点的子树总数
int dfs(int u) {
    st[u] = true;
    
    // 访问当前节点的记录变量
    int sum = 1, block = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {   // 枚举该节点的所有子节点
        int j = v[i];
        if (!st[j]) {
            int c = dfs(j);
            block = max(block, c); // 当前节点的最大子树
            sum += c;  // 记录子树总数
        }
    }
    block = max(block, n - sum);  // 最大的连通块
    res = min(res, block);
    return sum;
}

int main() {
    cin >> n;
    int a, b;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n; ++ i) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << res << endl;
    return 0;
}

图中点的层次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int h[N], v[M], ne[M], idx;
int d[N], q[N];
int n, m;

void add(int a, int b) {
    v[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs() {
    int hh = 0, rr = -1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    q[++ rr] = 1;
    int test = 1;
    while (hh <= rr) {
        
        int cur = q[hh ++];
        
        for (int i = h[cur]; i != -1; i = ne[i]){  // 枚举当前节点的所有子节点
            int j = v[i];
            
            if (d[j] == -1){  // 判断是否已访问
                d[j] = d[cur] + 1;
                q[++ rr] = j;
            }
        }
    }
    return d[n];
}

int main() {
    cin >> n >> m;
    int a, b;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; ++ i) {
        cin >> a >> b;
        add(a, b);
    }
    
    cout << bfs() << endl;
    
    return 0;
}

拓扑排序

拓扑序列一定是有向无环图，因此一定存在入度为0的点，如果从所有入度为0的点开始进入BFS访问，将访问过程中遇到的入度为0的点加入队列，则若存在拓扑序列应能遍历所有顶点，且入队的顺序就是一个拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10, M = N * 2;

int h[N], v[M], ne[M], idx;
int q[N], d[N]; // d保存每个顶点的入度
int n, m;

void add(int a, int b) {
    v[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int toposort() {
    int hh = 0, rr = -1;
    for (int i = 1; i <= n; ++ i) {  // 入度为0的顶点入队
        if (!d[i]) q[++ rr] = i;
    }
    
    while (hh <= rr) {
        int cur = q[hh ++];

        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = v[i];   // 获取该顶点
            -- d[j];
            if (!d[j]) q[++ rr] = j;  // 入度为0的点入队
        }
    }
    return rr == n - 1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int a, b;
    for(int i = 0; i < m; ++ i) {
        cin >> a >> b;
        add(a, b);
        d[b] ++;  // 入度+1
    }
    
    if (toposort()) {
        for (int i = 0; i < n; ++ i) {
            cout << q[i] << ' ';
        }cout << endl;
    }else {
        cout << -1 << endl;
    }
    return 0;
}

Dijkstra

Dijkstra用于计算一个节点到其他节点的最短路径。（单源最短路）
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。且在扩展过程中，贪心的选择这些点。

该算法要求图中『 不存在负权边 』。

  • 算法思想

两个集合S、U。S中为已确定最短路径的顶点，U中为未确定的，算法开始先将起点加入S，更新新加入的点对U中顶点到S的最短距离。然后不断循环从U中寻找到S最近的顶点，加入S、更新距离。直到全部加入S。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];   // 保存当前起点到每个顶点的最短距离！！！！
bool st[N];


int dijkstra() {
    memset(dist, 0x3f, sizeof dist);   // 假定数据小于10^9，0x3f3f3f3f就可当无穷大使用。这里可能出现无穷大+无穷大的情况
    dist[1] = 0;              // 起点
    
    for (int i = 0; i < n; ++ i) {  // 循环n次，每次找一个满足的顶点加入集合
        int t = -1;
        for (int j = 1; j <= n; ++ j)  // 枚举所有顶点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))  // 顶点不在已确定集合 中的最小的顶点
                t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= n; ++ j)  // 更新加入t顶点后的最短距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main() {
    cin >> n >> m;  // n个点、m条边
    
    memset(g, 0x3f, sizeof g);  // 邻接矩阵
    
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);  // 可能有重边
    }
    
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

在朴素版本的dijkstra中，查找未加入的点中距离最短的点的复杂度是O(n) 的，当顶点数很多时，容易超时，因此可以用堆来优化最短距离的查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;
using PII = pair<int, int>;

const int N = 1e5 + 10;
int dist[N];
bool st[N];
unordered_map<int, vector<PII>> graph;
int n, m;

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<>> heap; // 堆
    dist[1] = 0;
    heap.push({0, 1});
    
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        
        int distance = t.first, vertex = t.second;
        if (st[vertex]) continue;
        st[vertex] = true;
        
        for (auto & p : graph[vertex]) {
            int cur_dist = p.first, cur_ver = p.second;
            if (dist[cur_ver] > distance + cur_dist){
                dist[cur_ver] = distance + cur_dist;
                heap.push({dist[cur_ver], cur_ver});
            }
        }
    }
    
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main() {
    cin >> n >> m;
    int a, b, c;
    while (m --) {
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
    }
    
    cout << dijkstra() << endl;
    return 0;
}

公交路线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {    // 每趟路线都是回路，所以可以把每个公交车抽象成一个点，统计连通的点，构图+bfs
    int st,ed;
    vector<bool> visit;
    queue<int> q;
    unordered_map<int,bool> ans;
    vector<vector<int>> edg;
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if(S == T) return 0;
        // 排序，双指针建图 -->便于bfs
        int n = routes.size();
        edg.resize(n);
        for(int i=0;i<n;i++) sort(routes[i].begin(),routes[i].end()); //排序
        for(int i=0;i<n;i++){   // 找到S，T所在的点集
            for(int j=0;j<routes[i].size();j++){
                if(routes[i][j] == S) q.push(i);
                if(routes[i][j] == T) ans[i] = true;
            }
        }
        for(int i=0;i<n;i++){   // 双指针建图
            for(int j=i+1;j<n;j++){
                int l1 = 0,l2 = 0;
                while(l1 < routes[i].size() && l2 < routes[j].size()){
                    if(routes[i][l1]==routes[j][l2]){
                        edg[i].push_back(j);
                        edg[j].push_back(i);
                        break;
                    }else if(routes[i][l1] > routes[j][l2]) l2++;
                    else l1++;
                }
            }
        }


        // bfs按层搜索
        int cnt = 1;
        visit.resize(n,false);
        while(!q.empty()){
            int N=q.size();
            for(int i=0;i<N;i++){
                int t = q.front();
                q.pop();
                if(visit[t]) continue;
                visit[t] = true;
                if(ans.count(t)) return cnt;
                for(int i=0;i<edg[t].size();i++){
                    if(visit[edg[t][i]] == false) q.push(edg[t][i]);
                }
            }cnt++;
        }
        return -1;
    }
};